#include "algorithm.h"
#include <iostream>
#include <QDebug>
#include <QFile>
#include <QTextStream>
#include <QDebug>
#include "map.h"
#include <stdexcept>
#include <QStack>
#include <queue>
#include <QQueue>
#include <QElapsedTimer>
#include <QSet>
#include <QHash>


MatrixGraph::~MatrixGraph() {
    // 不需要手动释放邻接表中的内存
}



Edge::Edge() : m_from(-1), m_to(-1), price(0.0), timeC(0.0), details(nullptr) {}

Edge::Edge(int from, int to, double price, double timeC, std::shared_ptr<FlightDetails> details)
    : m_from(from), m_to(to), price(price), timeC(timeC), details(details) {}

int Edge::getFrom() const { return m_from; }
void Edge::setFrom(int from) { m_from = from; }
int Edge::getTo() const { return m_to; }
void Edge::setTo(int to) { m_to = to; }
double Edge::getPrice() const { return price; }
double Edge::getTimeC() const { return timeC; }

std::shared_ptr<FlightDetails> Edge::getDetails() const {
    if (!details) {
        throw std::runtime_error("Flight details not available");
    }
    return details;
}

QTime Edge::getDeTime() const {
    if (!details) {
        return QTime();
    }
    return details->deTime;
}

void Edge::setDeTime(QTime time) {
    if (details) {
        details->deTime = time;
    }
}

QTime Edge::getArrTime() const {
    if (!details) {
        return QTime();
    }
    return details->arrTime;
}

void Edge::setArrTime(QTime time) {
    if (details) {
        details->arrTime = time;
    }
}

QDate Edge::getDate() const {
    if (!details) {
        return QDate();
    }
    return details->date;
}

void Edge::setDate(QDate d) {
    if (details) {
        details->date = d;
    }
}

QString Edge::getAirline() const {
    if (!details) {
        return QString();
    }
    return details->airline;
}

QString Edge::getFlightNumber() const {
    if (!details) {
        return QString();
    }
    return details->flightNumber;
}

QString Edge::getDepartureAirport() const {
    if (!details) {
        return QString();
    }
    return details->deAirport;
}

QString Edge::getArrivalAirport() const {
    if (!details) {
        return QString();
    }
    return details->arrAirport;
}

double Edge::getOccupancy() const {
    if (!details) {
        return 0.0;
    }
    return details->occupancy;
}
double Edge::getWeight(int choose) const { return choose == 1 ? price : timeC; }



MatrixGraph::MatrixGraph() : m_vertices(0), m_edges(0) {}

void MatrixGraph::addCity(const QString& cityName) {
    if (cityIndexMap.find(cityName) == cityIndexMap.end()) {
        cityIndexMap[cityName] = m_vertices;
        adjList.push_back(std::vector<Edge>());
        m_vertices++;
        //qDebug() << "成功添加城市: " << cityName;
    } else {
        qDebug() << "城市已存在: " << cityName;
    }
}

void MatrixGraph::addEdge(const QString& fromCity, const QString& toCity, const QString& airline, const QString& flightNumber, const QString& deAirport,
                          const QString& arrAirport, QTime deTime, QTime arrTime, double price, double occupancy, double timeC, QDate date) {
    if (!cityIndexMap.contains(fromCity) || !cityIndexMap.contains(toCity)) {
        qDebug() << "城市未找到:" << fromCity << "或" << toCity;
        return;
    }

    int from = cityIndexMap[fromCity];
    int to = cityIndexMap[toCity];

    auto details = std::make_shared<FlightDetails>(airline, flightNumber, deAirport, arrAirport, deTime, arrTime, date, occupancy);
    adjList[from].emplace_back(from, to, price, timeC, details);

    /*qDebug() << "成功添加从" << fromCity << "到" << toCity << "的边，航空公司: " << airline << ", 航班编号: " << flightNumber
             << ", 起飞机场: " << deAirport << ", 降落机场: " << arrAirport << ", 起飞时间: " << deTime.toString()
             << ", 到达时间: " << arrTime.toString() << ", 价格: " << price << ", 上座率: " << occupancy << ", 时间消耗: " << timeC
             << ", 日期: " << date.toString();*/

    m_edges++;
}



QString MatrixGraph::Dijkstra(int choose, const QString& deCity, const QString& arrCity) {
    if (!cityIndexMap.contains(deCity) || !cityIndexMap.contains(arrCity)) {
        qDebug() << "起点或终点城市不存在。";
        return QString();
    }

    int start = cityIndexMap[deCity];
    int end = cityIndexMap[arrCity];
    const int maxDepth = 5;  // 最大转机次数，限制遍历深度
    const int minTransferTimeSecs = 30 * 60;  // 最少转机时间（30分钟）

    struct Node {
        int vertex;
        double distance;
        QTime arrivalTime;
        int depth;

        bool operator>(const Node& other) const {
            return distance > other.distance;
        }
    };

    std::vector<double> distances(m_vertices, std::numeric_limits<double>::infinity());
    std::vector<int> previous(m_vertices, -1);
    std::vector<QTime> arrivalTimes(m_vertices, QTime());
    std::vector<const Edge*> prevEdge(m_vertices, nullptr);  // 用于记录到达每个节点的航班信息
    distances[start] = 0;
    arrivalTimes[start] = QTime(0, 0);  // 初始到达时间为午夜

    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;
    pq.push(Node{start, 0, QTime(0, 0), 0});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        int u = current.vertex;

        if (u == end) break;

        if (current.depth > maxDepth) {
            continue;
        }

        for (const Edge& edge : adjList[u]) {
            int v = edge.getTo();
            double weight = edge.getWeight(choose);

            QTime currentArrivalTime = current.arrivalTime;
            QTime nextDepartureTime = edge.getDeTime();

            // 检查是否可以搭乘下一个航班（航班必须在到达时间之后，并且有足够的转机时间）
            if (currentArrivalTime.isValid() && currentArrivalTime.secsTo(nextDepartureTime) < minTransferTimeSecs) {
                continue;  // 起飞时间在到达时间之前或转机时间不足，无法搭乘
            }

            double newDistance = distances[u] + weight;
            if (newDistance < distances[v]) {
                distances[v] = newDistance;
                previous[v] = u;
                arrivalTimes[v] = edge.getArrTime();
                prevEdge[v] = &edge;  // 保存用于到达 v 的航班信息
                pq.push(Node{v, newDistance, edge.getArrTime(), current.depth + 1});
            }
        }
    }

    // 输出结果
    if (distances[end] == std::numeric_limits<double>::infinity()) {
        qDebug() << "无路径";
        return QString();
    } else {
        QString path;
        int at = end;
        while (previous[at] != -1) {
            int prev = previous[at];
            auto it = std::find_if(adjList[prev].begin(), adjList[prev].end(),
                                   [at](const Edge& edge) { return edge.getTo() == at; });

            if (it != adjList[prev].end()) {
                const Edge& edge = *it;
                path.prepend(QString("航班: %1, 航空公司: %2, 起飞机场: %3, 降落机场: %4, 起飞时间: %5, 到达时间: %6, 价格: %7, 上座率: %8\n")
                             .arg(edge.getFlightNumber()).arg(edge.getAirline()).arg(edge.getDepartureAirport()).arg(edge.getArrivalAirport())
                             .arg(edge.getDeTime().toString()).arg(edge.getArrTime().toString()).arg(edge.getPrice()).arg(edge.getOccupancy()));
            }
            at = prev;
        }

        path += QString("总%1: %2").arg(choose == 1 ? "价格" : "时间").arg(distances[end]);

        //qDebug() << path;
        return path;
    }
}


QList<FlightJourney> MatrixGraph::findAllPaths(const QString& startCity, const QString& endCity, int maxTransfers) {

    //qDebug() << "init";
    struct PathNode {
        QStringList pathList;             // 用于记录经过的城市路径
        int currentTransfers;             // 当前转机次数
        int currentCityIndex;             // 当前城市的索引
        QList<FlightSegment> segments;    // 每一段航班信息
        QTime lastArrivalTime;            // 上一次航班的到达时间
    };

    QQueue<PathNode> pathQueue;
    QList<FlightJourney> journeys;  // 存储最终找到的旅程列表
    QElapsedTimer timer;
    timer.start();

    // 初始化队列
    if (!cityIndexMap.contains(startCity)) {
        qWarning() << "Start city not found in cityIndexMap:" << startCity;
        return journeys;
    }

    pathQueue.enqueue({QStringList() << startCity, 0, cityIndexMap[startCity], QList<FlightSegment>(), QTime()});
    QHash<QString, bool> visitedPaths;  // 路径访问签名缓存，防止重复路径

    // 使用队列进行广度优先搜索
    while (!pathQueue.isEmpty()) {
        if (timer.elapsed() > 10000) {  // 超过 10 秒的时间限制，防止内存问题
            qDebug() << "路径查找超时，提前终止。";
            break;
        }

        PathNode currentNode = pathQueue.dequeue();
        QStringList pathList = currentNode.pathList;
        int currentCityIndex = currentNode.currentCityIndex;

        // 检查当前城市索引的有效性
        if (currentCityIndex < 0 || currentCityIndex >= adjList.size()) {
            qWarning() << "Invalid city index:" << currentCityIndex;
            continue;
        }

        QString currentCity = cityIndexMap.key(currentCityIndex);
        //qDebug() << "Current Node: City =" << currentCity << ", Path List =" << pathList.join("->");

        // 如果当前节点是目标城市，则构造完整路径
        if (currentCity == endCity) {
            FlightJourney journey;
            journey.startCity = startCity;
            journey.endCity = endCity;
            //qDebug()<<"journey:"<<journey.startCity<<"and"<<journey.endCity;
            journey.segments = currentNode.segments;
            journey.totalPrice = std::accumulate(journey.segments.begin(), journey.segments.end(), 0.0,
                                                 [](double sum, const FlightSegment& seg) { return sum + seg.price; });
            journey.totalMinutes = journey.getTotalTime();
            //qDebug() << "Adding Journey: Total Price =" << journey.totalPrice << ", Segments Count =" << journey.segments.size();
            journeys.append(journey);
            continue;
        }

        // 如果转机次数超过最大次数，则跳过该路径
        if (currentNode.currentTransfers > maxTransfers) {
            //qDebug() << "Exceeded max transfers for path:" << pathList.join("->");
            continue;
        }

        // 防止重复访问相同的路径
        QString currentPathSignature = currentNode.pathList.join("->") + QString::number(currentNode.currentTransfers);
        if (visitedPaths.contains(currentPathSignature)) {
            //qDebug() << "Path already visited:" << currentPathSignature;
            continue;
        }
        visitedPaths[currentPathSignature] = true;

        // 遍历邻接表中的所有边
        for (const Edge& edge : adjList[currentCityIndex]) {
            int nextCityIndex = edge.getTo();
            QString nextCity = cityIndexMap.key(nextCityIndex);

            // 检查转机时间
            if (currentNode.lastArrivalTime.isValid() && currentNode.lastArrivalTime.secsTo(edge.getDeTime()) < 30 * 60) {
                //qDebug() << "Transfer time too short from" << currentCity << "to" << nextCity;
                continue;  // 如果转机时间不足 30 分钟，则跳过
            }

            if (!pathList.contains(nextCity)) {
                // 更新路径信息
                QStringList newPathList = currentNode.pathList;
                newPathList.append(nextCity);

                // 构造新的航班段
                QList<FlightSegment> newSegments = currentNode.segments;

                FlightSegment newSegment;
                newSegment.fromCity = cityIndexMap.key(edge.getFrom());
                newSegment.toCity = cityIndexMap.key(edge.getTo());
                //qDebug()<<"segments:"<<newSegment.fromCity<<"and"<<newSegment.toCity;
                newSegment.flightNumber = edge.getFlightNumber();
                newSegment.airline = edge.getAirline();
                newSegment.departureAirport = edge.getDepartureAirport();
                newSegment.arrivalAirport = edge.getArrivalAirport();
                newSegment.departureTime = edge.getDeTime();
                newSegment.arrivalTime = edge.getArrTime();

                // 检查时间有效性
                if (!newSegment.departureTime.isValid() || !newSegment.arrivalTime.isValid()) {
                    qWarning() << "Invalid departure or arrival time for segment:" << newSegment.flightNumber;
                    continue; // 跳过无效时间的航段
                }


                newSegment.price = edge.getPrice();
                newSegment.isTransfer = (currentNode.currentTransfers > 0);

                newSegments.append(newSegment);

                // 将新路径节点加入队列
                pathQueue.enqueue({newPathList, currentNode.currentTransfers + 1, nextCityIndex, newSegments, edge.getArrTime()});
                //qDebug() << "Enqueued new path to city:" << nextCity << ", Current Transfers:" << currentNode.currentTransfers + 1;
            }
        }
    }

    return journeys;
}







